home *** CD-ROM | disk | FTP | other *** search
/ BBS in a Box 5 / BBS in a Box -Volume V (BBS in a Box) (April 1992).iso / Files / Prog / M / Mac gperf 1.9.cpt / Mac gperf 1.9 / src / keylist.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-03-11  |  34.3 KB  |  1,111 lines  |  [TEXT/KAHL]
  1. /* Routines for building, ordering, and printing the keyword list.
  2.    Copyright (C) 1989 Free Software Foundation, Inc.
  3.    written by Douglas C. Schmidt (schmidt@ics.uci.edu)
  4.  
  5. This file is part of GNU GPERF.
  6.  
  7. GNU GPERF is free software; you can redistribute it and/or modify
  8. it under the terms of the GNU General Public License as published by
  9. the Free Software Foundation; either version 1, or (at your option)
  10. any later version.
  11.  
  12. GNU GPERF is distributed in the hope that it will be useful,
  13. but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15. GNU General Public License for more details.
  16.  
  17. You should have received a copy of the GNU General Public License
  18. along with GNU GPERF; see the file COPYING.  If not, write to
  19. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  20.  
  21. #include <stdio.h>
  22. #include <assert.h>
  23. #include <stdlib.h>
  24. #include <string.h>
  25.  
  26. #include "options.h"
  27. #include "readline.h"
  28. #include "hashtable.h"
  29. #include "stderr.h"
  30. #include "xmalloc.h"
  31. #include "gperf.h"
  32. #include "perfect.h"
  33.  
  34. #include "keylist.h"
  35.  
  36.     /* Used in function reorder, below. */
  37.  
  38. static bool determined[ALPHABET_SIZE]; 
  39.  
  40.     /* Default type for generated code. */
  41.  
  42. static char *    default_array_type = "char *";
  43.  
  44.     /* Generated function ``in_word_set'' default return type. */
  45.     
  46. static char *    default_return_type = "char *";
  47.  
  48.     /* Largest positive integer value. */
  49.     /* Most negative integer value. */
  50.  
  51. #if 0
  52.     /* these are the original definitions, which don't work
  53.         under Think C (MAX_INT = -1, NEG_MAX_INT = 0). Think C has
  54.         16-bit ints, so the following values are correct */
  55.  
  56.     #define MAX_INT            ((~(unsigned)0)>>1)
  57.     #define NEG_MAX_INT        ((~(unsigned)0)^((~(unsigned)0)>>1))
  58. #else
  59.     #define MAX_INT            32767
  60.     #define NEG_MAX_INT        -32767
  61. #endif
  62.  
  63.     /* How wide the printed field width must be to contain the maximum hash value. */
  64.  
  65. static int        field_width = 2;
  66.  
  67.     /* Globally visible KEY_LIST object. */
  68.  
  69. KEY_LIST        key_list;
  70.  
  71. /*******************************************************************************\
  72. *                              Prototypes                                        *
  73. \*******************************************************************************/
  74.  
  75. static char *        get_special_input( char delimiter );
  76. static char *        save_include_src( void );
  77. static char *        get_array_type( void );
  78. static void            set_output_types( void );
  79. static LIST_NODE *    merge( LIST_NODE * list1, LIST_NODE * list2 );
  80. static LIST_NODE *    merge_sort( LIST_NODE * head );
  81. static int            get_occurrence( LIST_NODE * ptr );
  82. static void            set_determined( LIST_NODE * ptr );
  83. static bool            already_determined( LIST_NODE * ptr );
  84. static int            print_min_max( void );
  85. static void            print_switch( void );
  86. static void            print_keylength_table( void );
  87. static void            print_keyword_table( void );
  88. static void            print_hash_function( int max_hash_value );
  89. static void            print_lookup_function( void );
  90. static void            dump( void );
  91.  
  92.  
  93.     /***********************************************************************\
  94.     *                                                                        *
  95.     * name:        get_special_input                                            *
  96.     *                                                                        *
  97.     * descr:    Gathers the input stream into a buffer.                        *
  98.     *                                                                        *
  99.     \***********************************************************************/
  100.  
  101. /* Gathers the input stream into a buffer until one of two things occur:
  102.  
  103.    1. We read a '%' followed by a '%'
  104.    2. We read a '%' followed by a '}'
  105.  
  106.    The first symbolizes the beginning of the keyword list proper,
  107.    The second symbolizes the end of the C source code to be generated
  108.    verbatim in the output file.
  109.  
  110.    I assume that the keys are separated from the optional preceding struct
  111.    declaration by a consecutive % followed by either % or } starting in 
  112.    the first column. The code below uses an expandible buffer to scan off 
  113.    and return a pointer to all the code (if any) appearing before the delimiter. */
  114.  
  115. static char * get_special_input( char delimiter )
  116. { 
  117.     int            size  = 80;
  118.     char *        buf = xmalloc( size );
  119.     int            c;
  120.     int            i;
  121.  
  122.     for ( i = 0; ( c = getc( KeyFile ) ) != EOF; i++ )
  123.     {
  124.         if ( c == '%' )
  125.         {
  126.             if ( ( c = getc( KeyFile ) ) == delimiter )
  127.             {
  128.                 while ( ( c = getc( KeyFile ) ) != '\n' )
  129.                     ; /* Discard newline. */
  130.  
  131.                 if ( i == 0 )
  132.                     return "";
  133.                 else
  134.                 {
  135.                     buf[ delimiter == '%' && buf[i - 2] == ';' ? i - 2 : i - 1 ] = '\0';
  136.                     return buf;
  137.                 }
  138.             }
  139.             else
  140.                 ungetc( c, KeyFile );
  141.         }
  142.         else if ( i >= size )        /* Yikes, time to grow the buffer! */
  143.         { 
  144.             char *    temp = xmalloc( size *= 2 );
  145.             int        j;
  146.  
  147.             for ( j = 0; j < i; j++ )
  148.                 temp[ j ] = buf[ j ];
  149.  
  150.             free( buf );
  151.             buf = temp;
  152.         }
  153.         buf[  i] = c;
  154.     }
  155.  
  156.     return NULL;        /* Problem here. */
  157. }
  158.  
  159.     /***********************************************************************\
  160.     *                                                                        *
  161.     * name:        save_include_src                                            *
  162.     *                                                                        *
  163.     * descr:    Stores any C text that must be included verbatim into         *
  164.     *            the generated code output.                                    *
  165.     *                                                                        *
  166.     \***********************************************************************/
  167.  
  168. static char * save_include_src()
  169. {
  170.     int        c;
  171.   
  172.     if ( ( c = getc( KeyFile ) ) != '%' )
  173.     {
  174.         ungetc( c, KeyFile );
  175.         return "";
  176.     }
  177.     else if ( ( c = getc( KeyFile ) ) != '{' )
  178.         report_error( "internal error, %c != '{' on line %d in file %s%a",
  179.                         c, __LINE__, __FILE__);
  180.  
  181.         /* NOT REACHED */
  182.  
  183.     else 
  184.         return get_special_input( '}' );
  185. }
  186.  
  187.  
  188.     /***********************************************************************\
  189.     *                                                                        *
  190.     * name:        strcspn                                                        *
  191.     *                                                                        *
  192.     * descr:    description                                                    *
  193.     *                                                                        *
  194.     \***********************************************************************/
  195.  
  196. #if 0
  197.     /* the following is in the ANSI library */
  198.     
  199. /* strcspn - find length of initial segment of s consisting entirely
  200.    of characters not from reject (borrowed from Henry Spencer's
  201.    ANSI string package). */
  202.  
  203. static int
  204. strcspn (s, reject)
  205.      char *s;
  206.      char *reject;
  207. {
  208.   char *scan;
  209.   char *rej_scan;
  210.   int   count = 0;
  211.  
  212.   for (scan = s; *scan; scan++) 
  213.     {
  214.  
  215.       for (rej_scan = reject; *rej_scan;) 
  216.         if (*scan == *rej_scan++)
  217.           return count;
  218.  
  219.       count++;
  220.     }
  221.  
  222.   return count;
  223. }
  224. #endif
  225.  
  226.  
  227.     /***********************************************************************\
  228.     *                                                                        *
  229.     * name:        get_array_type                                                *
  230.     *                                                                        *
  231.     * descr:    Determines from the input file whether the user wants to    *
  232.     *            build a table from a user-defined struct, or whether the    *
  233.     *            user is content to simply use the default array of keys.    *
  234.     *                                                                        *
  235.     \***********************************************************************/
  236.  
  237. static char * get_array_type()
  238. {
  239.     return get_special_input ('%');
  240. }
  241.  
  242.     /***********************************************************************\
  243.     *                                                                        *
  244.     * name:        set_output_types                                            *
  245.     *                                                                        *
  246.     * descr:    Sets up the Return_Type, the Struct_Tag type and the         *
  247.     *            Array_Type based on various user options.                    *
  248.     *                                                                        *
  249.     \***********************************************************************/
  250.  
  251. static void set_output_types()
  252. {
  253.   
  254.   if (OPTION_ENABLED (option, TYPE) && !(key_list.array_type = get_array_type ()))
  255.     return;                     /* Something's wrong, bug we'll catch it later on.... */
  256.   else if (OPTION_ENABLED (option, TYPE))        /* Yow, we've got a user-defined type... */
  257.     {    
  258.       int struct_tag_length = strcspn (key_list.array_type, "{\n\0");
  259.       
  260.       if (OPTION_ENABLED (option, POINTER))      /* And it must return a pointer... */
  261.         {    
  262.           key_list.return_type = xmalloc (struct_tag_length + 2);
  263.           strncpy (key_list.return_type, key_list.array_type, struct_tag_length);
  264.           key_list.return_type[struct_tag_length] = '\0';
  265.           strcat (key_list.return_type, "*");
  266.         }
  267.       
  268.       key_list.struct_tag = (char *) xmalloc (struct_tag_length + 1);
  269.       strncpy (key_list.struct_tag, key_list.array_type, struct_tag_length);
  270.       key_list.struct_tag[struct_tag_length] = '\0';
  271.     }  
  272.   else if (OPTION_ENABLED (option, POINTER))     /* Return a char *. */
  273.     key_list.return_type = default_array_type;
  274. }
  275.  
  276.     /***********************************************************************\
  277.     *                                                                        *
  278.     * name:        read_keys                                                    *
  279.     *                                                                        *
  280.     * descr:    Read in all the keys from the input file and create a         *
  281.     *            linked list pointed to by Head. This list is then             *
  282.     *            quickly checked for "links", ie unhashable elements         *
  283.     *            possessing identical key sets and lengths.                    *
  284.     *                                                                        *
  285.     \***********************************************************************/
  286.  
  287. void read_keys()
  288. {
  289.     char *            ptr;
  290.     LIST_NODE *        temp;
  291.     LIST_NODE *        trail;
  292.   
  293.     key_list.include_src = save_include_src();
  294.     set_output_types();
  295.  
  296.         /*
  297.         **    Make sure that the input file is ok
  298.         */
  299.         
  300.     if ( ! ( ptr = read_line() ) ) 
  301.         report_error ("No words in input file, did you forget to prepend %s or use -t accidentally?\n%a", "%%");
  302.  
  303.         /*
  304.         **    Read in all the keywords from the input file.
  305.         */
  306.  
  307.     key_list.head = make_list_node( ptr, strcspn( ptr, ",\n" ) );
  308.     for ( temp = key_list.head; ( ptr = read_line() ) && strcmp( ptr, "%%" ); temp = temp->next )
  309.     {
  310.         temp->next = make_list_node( ptr, strcspn( ptr, ",\n") );
  311.         key_list.total_keys++;
  312.     }
  313.       
  314.         /* See if any additional C code is included at end of this file. */
  315.  
  316.     if ( ptr )
  317.         key_list.additional_code = TRUE;
  318.  
  319.  
  320.     {
  321.         bool    link = FALSE;            /* If this becomes TRUE we've got a link. */
  322.         int        table_multiple = 5;        /* hash table size multiplier times # keywords */
  323.  
  324.             /* Make large hash table for efficiency. */
  325.  
  326.         hash_table_init( (key_list.list_len = key_list.total_keys) * table_multiple ); 
  327.  
  328.             /*    Test whether there are any links and also set the maximum length of
  329.                 an identifier in the keyword list.        */
  330.       
  331.         for ( temp = key_list.head, trail = NULL; temp; temp = temp->next )
  332.         {
  333.             LIST_NODE *        ptr = retrieve( temp, OPTION_ENABLED( option, NOLENGTH ) );
  334.           
  335.                 /*    Check for links.  We deal with these by building an equivalence class
  336.                     of all duplicate values (i.e., links) so that only 1 keyword is
  337.                     representative of the entire collection.  This *greatly* simplifies
  338.                     processing during later stages of the program.        */
  339.  
  340.             if ( ptr )              
  341.             {                   
  342.                 key_list.list_len--;
  343.                 trail->next = temp->next;
  344.                 temp->link  = ptr->link;
  345.                 ptr->link   = temp;
  346.                 link        = TRUE;
  347.  
  348.                     /* Complain if user hasn't enabled the duplicate option. */
  349.             
  350.                 if ( !OPTION_ENABLED( option, DUP ) )
  351.                     report_error( "Key link: \"%s\" = \"%s\", with key set \"%s\".\n",
  352.                                     temp->key, ptr->key, temp->key_set );
  353.                 else if ( OPTION_ENABLED( option, DEBUG ) )
  354.                     report_error( "Key link: \"%s\" = \"%s\", with key set \"%s\".\n",
  355.                                       temp->key, ptr->key, temp->key_set );                
  356.             }
  357.             else
  358.                 trail = temp;
  359.             
  360.                 /*    Update minimum and maximum keyword length, if needed. */
  361.         
  362.             if ( temp->length > key_list.max_key_len ) 
  363.                 key_list.max_key_len = temp->length;
  364.             if ( temp->length < key_list.min_key_len ) 
  365.                 key_list.min_key_len = temp->length;
  366.         }
  367.  
  368.             /*    Exit program if links exists and option[DUP] not set,
  369.                 since we can't continue */
  370.  
  371.         if ( link ) 
  372.         {
  373.             if ( OPTION_ENABLED( option, DUP ) )
  374.             {
  375.                 if ( !OPTION_ENABLED( option, SWITCH ) )
  376.                 {
  377.                     report_error( "turning on -S option.\n" );
  378.                     SET_OPTION( option, SWITCH );
  379.                 }
  380.                 report_error( "Some input keys have identical hash values, examine"
  381.                               "output carefully...\n" );
  382.             }
  383.             else
  384.                 report_error( "Some input keys have identical hash values,\n"
  385.                               "try different key positions or use option -D.\n%a" );
  386.         }
  387.         else if ( OPTION_ENABLED( option, DUP ) )
  388.         {
  389.                 /*    If no links, clear the DUP option so we can use the length
  390.                           table, if output.        */
  391.  
  392.             UNSET_OPTION( option, DUP );
  393.         }
  394.     }
  395. }
  396.  
  397.  
  398.     /***********************************************************************\
  399.     *                                                                        *
  400.     * name:        merge                                                        *
  401.     *                                                                        *
  402.     * descr:    Recursively merges two sorted lists together to form one    *
  403.     *            sorted list. The ordering criteria is by frequency of         *
  404.     *            occurrence of elements in the key set or by hash value.     *
  405.     *                                                                        *
  406.     * note:        This is a kludge, but permits nice sharing of almost         *
  407.     *            identical code without incurring the overhead of a             *
  408.     *            function call comparison.                                    *
  409.     *                                                                        *
  410.     \***********************************************************************/
  411.   
  412. static LIST_NODE * merge( LIST_NODE * list1, LIST_NODE * list2 )
  413. {
  414.   if (!list1)
  415.     return list2;
  416.   else if (!list2)
  417.     return list1;
  418.   else if (key_list.occurrence_sort && list1->occurrence < list2->occurrence
  419.            || key_list.hash_sort && list1->hash_value > list2->hash_value)
  420.     {
  421.       list2->next = merge (list2->next, list1);
  422.       return list2;
  423.     }
  424.   else
  425.     {
  426.       list1->next = merge (list1->next, list2);
  427.       return list1;
  428.     }
  429. }
  430.  
  431. /* Applies the merge sort algorithm to recursively sort the key list by
  432.    frequency of occurrence of elements in the key set. */
  433.   
  434. static LIST_NODE * merge_sort( LIST_NODE * head )
  435. { 
  436.   if (!head || !head->next)
  437.     return head;
  438.   else
  439.     {
  440.       LIST_NODE *middle = head;
  441.       LIST_NODE *temp   = head->next->next;
  442.     
  443.       while (temp)
  444.         {
  445.           temp   = temp->next;
  446.           middle = middle->next;
  447.           if (temp)
  448.             temp = temp->next;
  449.         } 
  450.     
  451.       temp         = middle->next;
  452.       middle->next = NULL;
  453.       return merge (merge_sort (head), merge_sort (temp));
  454.     }   
  455. }
  456.  
  457. /* Returns the frequency of occurrence of elements in the key set. */
  458.  
  459. static int get_occurrence( LIST_NODE * ptr )
  460. {
  461.   int   value = 0;
  462.   char *temp;
  463.  
  464.   for (temp = ptr->key_set; *temp; temp++)
  465.     value += occurrences[*temp];
  466.   
  467.   return value;
  468. }
  469.  
  470. /* Enables the index location of all key set elements that are now 
  471.    determined. */
  472.   
  473. static void set_determined( LIST_NODE * ptr )
  474. {
  475.   char *temp;
  476.   
  477.   for (temp = ptr->key_set; *temp; temp++)
  478.     determined[*temp] = TRUE;
  479.   
  480. }
  481.  
  482. /* Returns TRUE if PTR's key set is already completely determined. */
  483.  
  484. static bool already_determined( LIST_NODE * ptr )
  485. {
  486.   bool  is_determined = TRUE;
  487.   char *temp;
  488.  
  489.   for (temp = ptr->key_set; is_determined && *temp; temp++)
  490.     is_determined = determined[*temp];
  491.   
  492.   return is_determined;
  493. }
  494.  
  495. /* Reorders the table by first sorting the list so that frequently occuring 
  496.    keys appear first, and then the list is reorded so that keys whose values 
  497.    are already determined will be placed towards the front of the list.  This
  498.    helps prune the search time by handling inevitable collisions early in the
  499.    search process.  See Cichelli's paper from Jan 1980 JACM for details.... */
  500.  
  501. void reorder()
  502. {
  503.   LIST_NODE *ptr;
  504.  
  505.   for (ptr = key_list.head; ptr; ptr = ptr->next)
  506.     ptr->occurrence = get_occurrence (ptr);
  507.   
  508.   key_list.hash_sort       = FALSE;
  509.   key_list.occurrence_sort = TRUE;
  510.   
  511.   for (ptr = key_list.head = merge_sort (key_list.head); ptr->next; ptr = ptr->next)
  512.     {
  513.       set_determined (ptr);
  514.     
  515.       if (already_determined (ptr->next))
  516.         continue;
  517.       else
  518.         {
  519.           LIST_NODE *trail_ptr = ptr->next;
  520.           LIST_NODE *run_ptr   = trail_ptr->next;
  521.       
  522.           for (; run_ptr; run_ptr = trail_ptr->next)
  523.             {
  524.         
  525.               if (already_determined (run_ptr))
  526.                 {
  527.                   trail_ptr->next = run_ptr->next;
  528.                   run_ptr->next   = ptr->next;
  529.                   ptr = ptr->next = run_ptr;
  530.                 }
  531.               else
  532.                 trail_ptr = run_ptr;
  533.             }
  534.         }
  535.     }     
  536. }
  537.  
  538. /* Determines the maximum and minimum hash values.  One notable feature is 
  539.    Ira Pohl's optimal algorithm to calculate both the maximum and minimum
  540.    items in a list in O(3n/2) time (faster than the O (2n) method). 
  541.    Returns the maximum hash value encountered. */
  542.   
  543. static int print_min_max()
  544. {
  545.     int            min_hash_value;
  546.     int            max_hash_value;
  547.     LIST_NODE *    temp;
  548.  
  549.         /*
  550.         **    If the list is odd, preprocess first item
  551.         **    (rest of list then becomes even). Otherwise
  552.         **    just set up for search.
  553.         */
  554.  
  555.     if ( ODD( key_list.list_len ) )
  556.     {
  557.         min_hash_value    = max_hash_value = key_list.head->hash_value;
  558.         temp            = key_list.head->next;
  559.     }
  560.     else
  561.     {
  562.         min_hash_value = MAX_INT;
  563.         max_hash_value = NEG_MAX_INT;
  564.         temp           = key_list.head;
  565.     }
  566.  
  567.         /**
  568.         ***  Find max and min (search is optimal,
  569.         ***  takes O(3n/2) time).
  570.         **/
  571.  
  572.     for ( ; temp; temp = temp->next )
  573.     { 
  574.         static int        i;
  575.         int                key_2;
  576.         int                key_1 = temp->hash_value;
  577.  
  578.         temp  = temp->next;
  579.         key_2 = temp->hash_value;
  580.         i++;
  581.  
  582.         if ( key_1 < key_2 )
  583.         {
  584.             if ( key_1 < min_hash_value )
  585.                 min_hash_value = key_1;
  586.             if ( key_2 > max_hash_value )
  587.                 max_hash_value = key_2;
  588.         }
  589.         else
  590.         {
  591.             if ( key_2 < min_hash_value )
  592.                 min_hash_value = key_2;
  593.             if ( key_1 > max_hash_value )
  594.                 max_hash_value = key_1;
  595.         }
  596.     }
  597.  
  598.     printf( "\n"
  599.             "#define MIN_WORD_LENGTH %d\n"
  600.             "#define MAX_WORD_LENGTH %d\n"
  601.             "#define MIN_HASH_VALUE %d\n"
  602.             "#define MAX_HASH_VALUE %d\n"
  603.             "/*\n"
  604.             "%5d keywords\n"
  605.             "%5d is the maximum key range\n"
  606.             "*/\n"
  607.             "\n",
  608.             (int)( ( key_list.min_key_len == MAX_INT ) ? key_list.max_key_len : key_list.min_key_len ),
  609.             (int)key_list.max_key_len,
  610.             (int)min_hash_value,
  611.             (int)max_hash_value,
  612.             (int)key_list.total_keys,
  613.             (int)( max_hash_value - min_hash_value + 1 )
  614.           );
  615.  
  616.     return max_hash_value;
  617. }
  618.  
  619.  
  620.     /***********************************************************************\
  621.     *                                                                        *
  622.     * name:        print_switch                                                *
  623.     *                                                                        *
  624.     * descr:    Generates the output using a C switch. This trades             *
  625.     *            increased search time for decreased table space             *
  626.     *            (potentially *much* less space for sparse tables).            *
  627.     *                                                                        *
  628.     \***********************************************************************/
  629.  
  630. /*    If the user has specified their own struct in the keyword file *and*
  631.     they enable the POINTER option we have extra work to do.  The solution
  632.     here is to maintain a local static array of user defined struct's, as
  633.     with the Print_Lookup_Function.  Then we use for switch statements to
  634.     perform a strcmp or strncmp, returning 0 if the str fails to match, and
  635.     otherwise returning a pointer to appropriate index location in the local
  636.     static array. */
  637.  
  638. static void print_switch()
  639. {
  640.     char *        comp_buffer = 0;
  641.     int            pointer_and_type_enabled = OPTION_ENABLED( option, POINTER ) && OPTION_ENABLED( option, TYPE );
  642.     size_t        allocSize;
  643.     
  644.     if ( pointer_and_type_enabled )
  645.     {
  646.         allocSize = strlen ("*str == *resword->%s && !strncmp (str + 1, resword->%s + 1, len - 1)"
  647.                                              + 2 * strlen (GET_KEY_NAME (option)) + 1);
  648.                                              
  649.         comp_buffer = (char *) malloc( allocSize );
  650.  
  651.         sprintf( comp_buffer, OPTION_ENABLED (option, COMP)
  652.                 ? "*str == *resword->%s && !strncmp (str + 1, resword->%s + 1, len - 1)"
  653.                 : "*str == *resword->%s && !strcmp (str + 1, resword->%s + 1)", GET_KEY_NAME (option), GET_KEY_NAME (option));
  654.     }
  655.     else
  656.         comp_buffer = OPTION_ENABLED (option, COMP) 
  657.                     ? "*str == *resword && !strncmp (str + 1, resword + 1, len - 1)" 
  658.                     : "*str == *resword && !strcmp (str + 1, resword + 1)";
  659.  
  660.     printf( "  if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n    {\n\
  661.       register int key = %s (str, len);\n\n\
  662.       if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE)\n        {\n",
  663.           GET_HASH_NAME (option));
  664.  
  665.     /* Output each keyword as part of a switch statement indexed by hash value. */
  666.  
  667.     if (OPTION_ENABLED (option, POINTER) || OPTION_ENABLED (option, DUP))
  668.     {
  669.       LIST_NODE *temp;
  670.  
  671.       printf ("          %s%s *resword; %s\n\n          switch (key)\n            {\n",
  672.               OPTION_ENABLED (option, CONST) ? "const " : "",
  673.               pointer_and_type_enabled ? key_list.struct_tag : "char", 
  674.               OPTION_ENABLED (option, LENTABLE) && !OPTION_ENABLED (option, DUP) ? "int key_len;" : "");
  675.  
  676.       for (temp = key_list.head; temp; temp = temp->next)
  677.         {
  678.           printf ("            case %*d:\n", field_width, temp->hash_value);
  679.  
  680.           if (temp->link)
  681.             {
  682.               LIST_NODE *links;
  683.  
  684.               for (links = temp; links; links = links->link)
  685.                 {
  686.                   if (pointer_and_type_enabled)
  687.                     printf ("              resword = &wordlist[%d];\n", links->index);
  688.                   else
  689.                     printf ("              resword = \"%s\";\n", links->key); 
  690.                   printf ("              if (%s) return resword;\n", comp_buffer);
  691.                 }
  692.               printf ("              return 0;\n");
  693.             }
  694.           else if (temp->next && temp->hash_value == temp->next->hash_value)
  695.             {
  696.  
  697.               for ( ; temp->next && temp->hash_value == temp->next->hash_value;
  698.                    temp = temp->next)
  699.                 {
  700.                   if (pointer_and_type_enabled)
  701.                     printf ("              resword = &wordlist[%d];\n", temp->index);
  702.                   else
  703.                     printf ("              resword = \"%s\";\n", temp->key);
  704.                   printf ("              if (%s) return resword;\n", comp_buffer);
  705.                 }
  706.               if (pointer_and_type_enabled)
  707.                 printf ("              resword = &wordlist[%d];\n", temp->index);
  708.               else
  709.                 printf ("              resword = \"%s\";\n", temp->key);
  710.               printf ("              return %s ? resword : 0;\n", comp_buffer);
  711.             }
  712.           else 
  713.             {
  714.               if (pointer_and_type_enabled)
  715.                 printf ("              resword = &wordlist[%d];", temp->index);
  716.               else 
  717.                 printf ("              resword = \"%s\";", temp->key);
  718.               if (OPTION_ENABLED (option, LENTABLE) && !OPTION_ENABLED (option, DUP))
  719.                 printf (" key_len = %d;", temp->length);
  720.               printf (" break;\n");
  721.             }
  722.         }
  723.       printf ("            default: return 0;\n            }\n");
  724.       printf (OPTION_ENABLED (option, LENTABLE) && !OPTION_ENABLED (option, DUP)
  725.               ? "          if (len == key_len && %s)\n            return resword;\n"
  726.               : "          if (%s)\n            return resword;\n", comp_buffer);
  727.       printf ("      }\n  }\n  return 0;\n}\n");
  728.     }
  729.     else                          /* Nothing special required here. */
  730.     {                        
  731.         LIST_NODE *temp;
  732.  
  733.         printf ("          char *s = \"\";\n\n          switch (key)\n            {\n");
  734.       
  735.         for ( temp = key_list.head; temp; temp = temp->next )
  736.             if (OPTION_ENABLED (option, LENTABLE))
  737.                 printf ("            case %*d: if (len == %d) s = \"%s\"; else return 0; break;\n", 
  738.                   field_width, temp->hash_value, temp->length, temp->key);
  739.             else
  740.                 printf ("            case %*d: s = \"%s\"; break;\n",
  741.                   field_width, temp->hash_value, temp->key);
  742.  
  743.         printf( "            default: return 0;\n            }\n          return *s == *str && !%s;\n        }\n    }\n  return 0;\n}\n", 
  744.               OPTION_ENABLED (option, COMP) ? "strncmp (s + 1, str + 1, len - 1)" : "strcmp (s + 1, str + 1)");
  745.     }
  746.  
  747.     if ( comp_buffer )
  748.         free( comp_buffer );
  749. }
  750.  
  751.     /***********************************************************************\
  752.     *                                                                        *
  753.     * name:        print_keylength_table                                        *
  754.     *                                                                        *
  755.     * descr:    Prints out a table of keyword lengths, for use with the     *
  756.     *            comparsion code in generated function "in_word_set"            *
  757.     *                                                                        *
  758.     \***********************************************************************/
  759.  
  760. static void print_keylength_table()
  761. {
  762.   int        max_column = 15;
  763.   int        index      = 0;
  764.   int        column     = 0;
  765.   char      *indent     = OPTION_ENABLED (option, GLOBAL) ? "" : "  ";
  766.   LIST_NODE *temp;
  767.  
  768.   if (!OPTION_ENABLED (option, DUP) && !OPTION_ENABLED (option, SWITCH)) 
  769.     {
  770.       printf ("\n%sstatic %sunsigned %s lengthtable[] =\n%s%s{\n    ",
  771.               indent, OPTION_ENABLED (option, CONST) ? "const " : "",
  772.               key_list.max_key_len < 256 ? "char" :
  773.               (key_list.max_key_len < 65536 ? "short" : "long"),
  774.               indent, indent);
  775.   
  776.       for (temp = key_list.head; temp; temp = temp->next, index++)
  777.         {
  778.     
  779.           if (index < temp->hash_value)
  780.             {
  781.       
  782.               for ( ; index < temp->hash_value; index++)
  783.                 printf ("%3d%s", 0, ++column % (max_column - 1) ? "," : ",\n    ");
  784.             }
  785.     
  786.           printf ("%3d%s", temp->length, ++column % (max_column - 1 ) ? "," : ",\n    ");
  787.         }
  788.   
  789.       printf ("\n%s%s};\n\n", indent, indent);
  790.     }
  791. }
  792.  
  793. /* Prints out the array containing the key words for the Perfect
  794.    hash function. */
  795.   
  796. static void print_keyword_table()
  797. {
  798.   char      *l_brace      = *key_list.head->rest ? "{" : "";
  799.   char      *r_brace      = *key_list.head->rest ? "}," : "";
  800.   int        doing_switch = OPTION_ENABLED (option, SWITCH);
  801.   char      *indent       = OPTION_ENABLED (option, GLOBAL) ? "" : "  ";
  802.   int        index        = 0;
  803.   LIST_NODE *temp;
  804.  
  805.   printf ("\n%sstatic %s%s wordlist[] =\n%s%s{\n", 
  806.           indent, OPTION_ENABLED (option, CONST) ? "const " : "",
  807.           key_list.struct_tag, indent, indent);
  808.   
  809.   /* Generate an array of reserved words at appropriate locations. */
  810.   
  811.     for (temp = key_list.head; temp; temp = temp->next, index++)
  812.         {
  813.             temp->index = index;
  814.  
  815.             if (!doing_switch && index < temp->hash_value)
  816.                 {
  817.                     int column;
  818.  
  819.                     printf ("      ");
  820.       
  821.                     for (column = 1; index < temp->hash_value; index++, column++)
  822.                         printf ("%s\"\",%s %s", l_brace, r_brace, column % 9 ? "" : "\n      ");
  823.       
  824.                     if (column % 10)
  825.                         printf ("\n");
  826.                     else 
  827.                         {
  828.                             printf ("%s\"%s\", %s%s\n", l_brace, temp->key, temp->rest, r_brace);
  829.                             continue;
  830.                         }
  831.                 }
  832.  
  833.             printf ("      %s\"%s\", %s%s\n", l_brace, temp->key, temp->rest, r_brace);
  834.  
  835.             /* Deal with links specially. */
  836.             if (temp->link)
  837.                 {
  838.                     LIST_NODE *links;
  839.  
  840.                     for (links = temp->link; links; links = links->link)
  841.                         {
  842.                             links->index = ++index;
  843.                             printf ("      %s\"%s\", %s%s\n", l_brace, links->key, links->rest, r_brace);
  844.                         }
  845.                 }
  846.  
  847.         }
  848.  
  849.   printf ("%s%s};\n\n", indent, indent);
  850. }
  851.  
  852. /* Generates C code for the hash function that returns the
  853.    proper encoding for each key word. */
  854.  
  855. static void print_hash_function( int max_hash_value )
  856. {
  857.   int max_column = 10;
  858.   int count       = max_hash_value;
  859.  
  860.   /* Calculate maximum number of digits required for MAX_HASH_VALUE. */
  861.  
  862.   while ((count /= 10) > 0)
  863.     field_width++;
  864.  
  865.   if (OPTION_ENABLED (option, GNU))
  866.     printf ("#ifdef __GNUC__\ninline\n#endif\n");
  867.   
  868.   printf (OPTION_ENABLED (option, ANSI) 
  869.           ? "static int\n%s (register const char *str, register int len)\n{\n  static %sunsigned %s hash_table[] =\n    {"
  870.           : "static int\n%s (str, len)\n     register char *str;\n     register unsigned int  len;\n{\n  static %sunsigned %s hash_table[] =\n    {",
  871.           GET_HASH_NAME (option), OPTION_ENABLED (option, CONST) ? "const " : "",
  872.           max_hash_value < 256 ? "char" : (max_hash_value < 65536 ? "short" : "int"));
  873.   
  874.   for (count = 0; count < ALPHABET_SIZE; ++count)
  875.     {
  876.       if (!(count % max_column))
  877.         printf ("\n    ");
  878.       
  879.       printf ("%*d,", field_width, occurrences[count] ? asso_values[count] : max_hash_value);
  880.     }
  881.   
  882.   /* Optimize special case of ``-k 1,$'' */
  883.   if (OPTION_ENABLED (option, DEFAULTCHARS)) 
  884.     printf ("\n    };\n  return %s + hash_table[str[len - 1]] + hash_table[str[0]];\n}\n\n",
  885.             OPTION_ENABLED (option, NOLENGTH) ? "0" : "len");
  886.   else
  887.     {
  888.       int key_pos;
  889.  
  890.       RESET (option);
  891.  
  892.       /* Get first (also highest) key position. */
  893.       key_pos = GET (option); 
  894.       
  895.       /* We can perform additional optimizations here. */
  896.       if (!OPTION_ENABLED (option, ALLCHARS) && key_pos <= key_list.min_key_len) 
  897.         { 
  898.           printf ("\n  };\n  return %s", OPTION_ENABLED (option, NOLENGTH) ? "0" : "len");
  899.           
  900.           for ( ; key_pos != EOS && key_pos != WORD_END; key_pos = GET (option))
  901.             printf (" + hash_table[str[%d]]", key_pos - 1);
  902.            
  903.           printf ("%s;\n}\n\n", key_pos == WORD_END ? " + hash_table[str[len - 1]]" : "");
  904.         }
  905.  
  906.       /* We've got to use the correct, but brute force, technique. */
  907.       else 
  908.         {                    
  909.           printf ("\n    };\n  register int hval = %s ;\n\n  switch (%s)\n    {\n      default:\n",
  910.                   OPTION_ENABLED (option, NOLENGTH) ? "0" : "len", OPTION_ENABLED (option, NOLENGTH) ? "len" : "hval");
  911.           
  912.           /* User wants *all* characters considered in hash. */
  913.           if (OPTION_ENABLED (option, ALLCHARS)) 
  914.             { 
  915.               int i;
  916.  
  917.               for (i = key_list.max_key_len; i > 0; i--)
  918.                 printf ("      case %d:\n        hval += hash_table[str[%d]];\n", i, i - 1);
  919.               
  920.               printf ("    }\n  return hval;\n}\n\n");
  921.             }
  922.           else /* do the hard part... */
  923.             {                
  924.               count = key_pos + 1;
  925.               
  926.               do
  927.                 {
  928.                   
  929.                   while (--count > key_pos)
  930.                     printf ("      case %d:\n", count);
  931.                   
  932.                   printf ("      case %d:\n        hval += hash_table[str[%d]];\n", key_pos, key_pos - 1);
  933.                 }
  934.               while ((key_pos = GET (option)) != EOS && key_pos != WORD_END);
  935.               
  936.               printf ("    }\n  return hval%s ;\n}\n\n", key_pos == WORD_END ? " + hash_table[str[len - 1]]" : "");
  937.           }
  938.       }
  939.   }
  940. }
  941.  
  942. /* Generates C code to perform the keyword lookup. */
  943.  
  944. static void print_lookup_function()
  945. { 
  946.   printf ("  if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)\n    {\n\
  947.       register int key = %s (str, len);\n\n\
  948.       if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE)\n        {\n\
  949.           register %schar *s = wordlist[key]", 
  950.           GET_HASH_NAME (option), OPTION_ENABLED (option, CONST) ? "const " : "");
  951.   if (key_list.array_type != default_array_type)
  952.     printf (".%s", GET_KEY_NAME (option));
  953.  
  954.   printf (";\n\n          if (%s*s == *str && !%s)\n            return %s",
  955.           OPTION_ENABLED (option, LENTABLE) ? "len == lengthtable[key]\n              && " : "",
  956.           OPTION_ENABLED (option, COMP) ? "strncmp (str + 1, s + 1, len - 1)" : "strcmp (str + 1, s + 1)",
  957.           OPTION_ENABLED (option, TYPE) && OPTION_ENABLED (option, POINTER) ? "&wordlist[key]" : "s");
  958.   printf (";\n        }\n    }\n  return 0;\n}\n");
  959. }
  960.  
  961. /* Generates the hash function and the key word recognizer function
  962.    based upon the user's Options. */
  963.  
  964. void print_output()
  965. {
  966.   int global_table = OPTION_ENABLED (option, GLOBAL);
  967.  
  968.   printf ("/* C code produced by gperf version %s */\n", version_string);
  969.   print_options();
  970.   
  971.   printf ("%s\n", key_list.include_src);
  972.   
  973.   /* Potentially output type declaration now, reference it later on.... */
  974.   if (OPTION_ENABLED (option, TYPE) && !OPTION_ENABLED (option, NOTYPE)) 
  975.     printf ("%s;\n", key_list.array_type);
  976.   
  977.   print_hash_function (print_min_max ());
  978.   
  979.   if (global_table)
  980.     if (OPTION_ENABLED (option, SWITCH))
  981.       {
  982.         if (OPTION_ENABLED (option, LENTABLE) && OPTION_ENABLED (option, DUP))
  983.           print_keylength_table ();
  984.         if (OPTION_ENABLED (option, POINTER) && OPTION_ENABLED (option, TYPE))
  985.           print_keyword_table ();
  986.       }
  987.     else
  988.       {
  989.         if (OPTION_ENABLED (option, LENTABLE))
  990.           print_keylength_table ();
  991.         print_keyword_table ();
  992.       }
  993.   /* Use the inline keyword to remove function overhead. */
  994.   if (OPTION_ENABLED (option, GNU)) 
  995.     printf ("#ifdef __GNUC__\ninline\n#endif\n");
  996.   
  997.   /* Use ANSI function prototypes. */
  998.   printf (OPTION_ENABLED (option, ANSI)
  999.           ? "%s%s\n%s (register const char *str, register int len)\n{\n"
  1000.           : "%s%s\n%s (str, len)\n     register char *str;\n     register unsigned int len;\n{\n", 
  1001.             OPTION_ENABLED (option, CONST) ? "const " : "", 
  1002.             key_list.return_type, GET_FUNCTION_NAME (option));
  1003.   
  1004.   /* Use the switch in place of lookup table. */
  1005.   if (OPTION_ENABLED (option, SWITCH))
  1006.     {               
  1007.       if (!global_table)
  1008.         {
  1009.           if (OPTION_ENABLED (option, LENTABLE) && OPTION_ENABLED (option, DUP))
  1010.             print_keylength_table ();
  1011.           if (OPTION_ENABLED (option, POINTER) && OPTION_ENABLED (option, TYPE)) 
  1012.             print_keyword_table ();
  1013.         }
  1014.       print_switch ();
  1015.     }
  1016.   else                /* Use the lookup table, in place of switch. */
  1017.     {           
  1018.       if (!global_table)
  1019.         {
  1020.           if (OPTION_ENABLED (option, LENTABLE))
  1021.             print_keylength_table ();
  1022.           print_keyword_table ();
  1023.         }
  1024.       print_lookup_function ();
  1025.     }
  1026.  
  1027.         /*
  1028.         **    If there is additional code, read it from 
  1029.         **    the key file and write to output
  1030.         */
  1031.  
  1032.     if ( key_list.additional_code )
  1033.     {
  1034.         int        c;
  1035.  
  1036.         while ( ( c = getc( KeyFile ) ) != EOF )
  1037.             putchar( c );
  1038.     }
  1039. }
  1040.  
  1041.     /***********************************************************************\
  1042.     *                                                                        *
  1043.     * name:        sort                                                        *
  1044.     *                                                                        *
  1045.     * descr:    Sorts the keys by hash value                                *
  1046.     *                                                                        *
  1047.     \***********************************************************************/
  1048.  
  1049. void sort()
  1050. { 
  1051.     key_list.hash_sort       = TRUE;
  1052.     key_list.occurrence_sort = FALSE;
  1053.  
  1054.     key_list.head = merge_sort( key_list.head );
  1055. }
  1056.  
  1057. /* Dumps the key list to stderr stream. */
  1058.  
  1059. static void dump() 
  1060. {      
  1061.   LIST_NODE *ptr;
  1062.  
  1063.   report_error ("\nList contents are:\n(hash value, key length, index, key set, uniq set, key):\n");
  1064.   
  1065.   for (ptr = key_list.head; ptr; ptr = ptr->next)
  1066.     report_error ("      %d,      %d,     %d, %s, %s, %s\n",
  1067.                   ptr->hash_value, ptr->length, ptr->index,
  1068.                   ptr->key_set, ptr->uniq_set, ptr->key);
  1069. }
  1070.  
  1071. /* Simple-minded constructor action here... */
  1072.  
  1073. void key_list_init()
  1074. {   
  1075.   key_list.total_keys      = 1;
  1076.   key_list.max_key_len     = NEG_MAX_INT;
  1077.   key_list.min_key_len     = MAX_INT;
  1078.   key_list.return_type     = default_return_type;
  1079.   key_list.array_type      = key_list.struct_tag  = default_array_type;
  1080.   key_list.head            = NULL;
  1081.   key_list.additional_code = FALSE;
  1082. }
  1083.  
  1084. /* Returns the length of entire key list. */
  1085.  
  1086. int length() 
  1087. { 
  1088.   return key_list.list_len;
  1089. }
  1090.  
  1091. /* Returns length of longest key read. */
  1092.  
  1093. int max_key_length()
  1094. { 
  1095.   return key_list.max_key_len;
  1096. }
  1097.  
  1098. /* DESTRUCTOR dumps diagnostics during debugging. */
  1099.  
  1100. void key_list_destroy() 
  1101. { 
  1102.   if (OPTION_ENABLED (option, DEBUG))
  1103.     {
  1104.       report_error ("\nDumping key list information:\ntotal unique keywords = %d\
  1105. \ntotal keywords = %d\nmaximum key length = %d.\n", 
  1106.                     key_list.list_len, key_list.total_keys, key_list.max_key_len);
  1107.       dump ();
  1108.       report_error ("End dumping list.\n\n");
  1109.     }
  1110. }
  1111.